//
// Created by masaikk on 2020/12/28.
//

#ifndef COLK_SOLUTION_H
#define COLK_SOLUTION_H
#include <vector>
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) {
            return 0;
        }
        if (k > prices.size() / 2) {
            k = prices.size() / 2;
        }
        int dp[501][2] = {}; // 交易次数， 是否持存. 最多交易1000 / 2次
        for (int i = 0; i <= k; i ++) {
            dp[i][1] = -prices[0];
        }
        for (int i = 1; i < n; i ++) {
            if (k >= 1) {
                dp[k][0] = max(dp[k][0], dp[k - 1][1] + prices[i]);
            }
            for (int j = k - 1; j >= 1; j --) {
                dp[j][1] = max(dp[j][1], dp[j][0] - prices[i]);
                dp[j][0] = max(dp[j][0], dp[j - 1][1] + prices[i]);
            }
            dp[0][1] = max(dp[0][1], dp[0][0] - prices[i]);
        }
        return dp[k][0];
    }
    int max(int a,int b){
        if(a>=b){
            return a;
        } else{
            return b;
        }
    }
};

#endif //COLK_SOLUTION_H
